1 Abstract

2 Wprowadzenie

2.1 Motywacje i opis problemu

2.2 Wybrane struktury pamięciowe

2.3 Cel pracy

3 Implementacja struktur pamięciowych

3.1 Lista

3.1.1 Dodawanie

3.1.2 Odczyt

3.1.3 Odczyt sekwencyjny

3.1.4 Aktualizacja

3.1.5 Usuwanie

3.2 Słownik

3.2.1 Dodawanie

3.2.2 Odczyt

3.2.3 Odczyt sekwencyjny

3.2.4 Aktualizacja

3.2.5 Usuwanie

3.3 T-Drzewo

3.3.1 Dodawanie

3.3.2 Odczyt

3.3.3 Odczyt sekwencyjny

3.3.4 Aktualizacja

3.3.5 Usuwanie

4 Metodologia badań

W tym rozdziale zostanie opisana obrana metodologia badań uwzględniająca poszczególne operacje, środowisko oraz sposób przeprowadzenia badań.

4.1 Wybrane operacje

Do badań wybrano 6 różnych operacji:

  • Dodawanie - do istniejącej bazy danych dodano n różnych nowych wartości o kolejnych wartościach indeksu, rozpoczynających się od wartości większej o 1 od największej obecnie istniejących. Pod każdy z kluczy generowano losowo dane osoby (imię, nazwisko, numer PESEL, adres mailowy, numer telefonu, wiek oraz adres).

  • Odczyt - do odczytu wybierano każdorazowo losową wartość ze wszystkich wartości indeksu bazy danych.

  • Odczyt sekwencyjny - do odczytu wybierano każdorazowo losową wartość początkową przedziału. Na jej podstawie każdorazowo dokonano 100 odczytów sekwencyjnych wartości kluczy.

  • Aktualizacja - do aktualizacji wybierano każdorazowo losową wartość ze wszystkich wartości indeksu bazy danych, a następnie dokonywano ponownego generowania danych osoby.

  • Usuwanie - do usuwania wybrano każdorazowo losową wartość, od wartości minimalnej, do maksymalnej z bazy danych. Niektóre odczyty mogły próbować usunąć wartość nieistniejącą.

  • Połączenie operacji - operacja składająca się z łańcucha 600 operacji odczytu z całej bazy danych, 600 operacji dodania wartości o nowych indeksach wzorem operacji dodania oraz 600 operacji usunięcia dodanych przed chwilą danych.

4.2 Przeprowadzone badania

W celu uzyskania miarodajnych wyników, objęto poniższą metodologie badań.

Każda z operacji została wykonana 3000 razy pod rząd, w celu uniknięcia tzw. outlayerów, mierząc czas wykonania zbioru operacji. Pozwoliło to osiągnąć uśrednione czasy dla każdej z operacji. W czas operacji jest również wliczony losowy wybór wartości z przedziału zależnego od wielkości danych.

Sekwencje operacji zostały uruchomione na bazach danych z różną, początkową ilością danych. zaczynając na 10,000 rekordach, kończąc na 100,000 z krokiem 10,000.

W celu zminimalizowania wpływu usług uruchamianych przez system w tle niezależnie od użytkownika, generując outlayery, cały proces został wykonany 3 razy, pozwalając na uśrednienie wyników badań.

4.3 Opis środowiska

Środowisko do przeprowadzenia badań stanowi komputer wyposażony w:

  • Procesor Ryzen 5 3600
  • 16 GB pamięci DDR4 o taktowaniu 3200 MHz
  • System Windows 11 w wersji 21H2
  • Python w wersji 3.11.1

W ramach przeprowadzanych badań, nie dokonywano żadnych operacji na wyżej wymienionym systemie.

5 Wyniki badań

W tej sekcji zawiera się wizualizacja oraz opis wyników przeprowadzonych badań.

5.1 Dodawanie danych

Zauważyć można, że w procesie dodawania najwolniejsza jest baza danych oparta na liście, gdzie jej złożoność rośnie mniej-więcej liniowo.

Następna w kolejności jak chodzi o prędkość jest baza oparta na t-drzewie dla węzła o wielkości 100, którego złożoność rożnie mniej więcej liniowo W przypadku dwóch pozostałych baz opartych na t-drzewach zauważyć można, że rosną one bardzo powoli.

Najszybszą operację dodawania posiada baza oparta na słowniku, której to czas odczytu jest stały.

5.2 Odczyt losowy danych

Operacje odczytu losowego prezentują się podobie do operacji dodawania danych.

Najwolniejszy odczyt posiada struktura listowa, następnie struktury oparte na t-drzewie, a najszybsza jest struktura oparta na słowniku, która to jest jedyna niezależna od wielkości bazy danych.

5.3 Odczyt sekwencyjny danych

Operacja odczytu sekwencyjnego na bazie opartej na słowniku jest najwolniejsza. Nieznacznie szybsza jest ta oparta na liście oraz na t-drzewie z węzłem o wielkości 100.

Znacznie szybsze są struktury oparte na t-drzewie z węzłami o wielkościach 500 oraz 1000.

Wszystkie struktury wykazały tutaj złożoność liniową.

5.4 Aktualizacja danych

Zdecydowanie najwolniejszą strukturą do tej operacji jest lista, której to złożoność rośnie liniowo.

Wszystkie pozostałe struktury wykonują tą operację znacznie szybciej. Jednak warto zauważyć, że poza listą, t-drzewo z węzłem o wielkości 100 widocznie zależy od wielkości bazy danych.

5.5 Usuwanie danych

Usuwanie danych z listy zajmuje najwięcej czasu i rośnie ono liniowo.

Następna jest baza oparta na t-drzewie o wielkości 100, 1000 oraz 500, które rosną logarytmicznie.

Najszybsze jest operowanie na strukturze słownika, które rośnie nieznacznie w zależności od wielkości bazy danych.

5.6 Połączenie operacji

Połączenie operacji prezentuje się analogicznie do wykresu operacji dodawania, gdzie operowanie na liście zajmuje najdłużej, następnie jest operowanie na t-drzewie o węźle z wielkością 100, 1000, 500 oraz na słowniku.

6 Zakończenie

6.1 Podsumowanie prac i wnioski

7 Literatura